package pers.qianyu.month_202101.date_20210111;

import org.junit.*;

import java.util.*;

/**
 * 130. 被围绕的区域
 * https://leetcode-cn.com/problems/surrounded-regions/
 * DFS 解决方法
 *
 * @author mizzle rain
 * @date 2021-01-11 17:47
 */
public class SurroundedRegions {
    int[][] dxy = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

    public void solve(char[][] board) {
        int h = board.length;
        if (h == 0) return;
        int w = board[0].length;
        if (w == 0) return;

        for (int i = 0; i < h; i++) {
            if (board[i][0] == 'O') dfs(board, i, 0);
            if (board[i][w - 1] == 'O') dfs(board, i, w - 1);
        }
        for (int i = 0; i < w; i++) {
            if (board[0][i] == 'O') dfs(board, 0, i);
            if (board[h - 1][i] == 'O') dfs(board, h - 1, i);
        }

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (board[i][j] == '1') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }

    private void dfs(char[][] board, int i, int j) {
        int h = board.length;
        int w = board[0].length;
        board[i][j] = '1';
        for (int[] d : dxy) {
            int x = i + d[0], y = j + d[1];
            if (x >= 0 && y >= 0 && x < h && y < w && board[x][y] == 'O') {
                dfs(board, x, y);
            }
        }
    }

    @Test
    public void test1() {
        char[][] arr = {
                {'O', 'O'},
                {'O', 'O'},
        };
        new SurroundedRegions().solve(arr);
        Arrays.stream(arr).forEach(i -> System.out.println(Arrays.toString(i)));
    }

    @Test
    public void test2() {
        char[][] arr = {
                {'O', 'O', 'O'},
                {'O', 'O', 'O'},
                {'O', 'O', 'O'},
        };
        new SurroundedRegions().solve(arr);
        Arrays.stream(arr).forEach(i -> System.out.println(Arrays.toString(i)));
    }
}
